7.复杂数据处理 · 树形

7.复杂数据处理 · 树形

什么是树形结构？树形结构无论是在计算机环境中，还是在我们的日常生活中都非常的常见，比如我们电脑中的文件夹结构、比如公司内部的人员结构，都是呈上一级元素和若干下一级元素组成的高维度结构。

为了能够在计算机程序中实现对树形结构的操作处理，工程师们发明了非常多不同种类的树形结构以及适合于它们的各种算法。但是我们这里不需要太深入地了解这些各式各样的结构和算法，我们只需要学习最朴素的简单树形即可。

当然如果有兴趣的话，您也可以通过《算法》、《算法导论》、《编程珠玑》等等经典的算法教材来学习更多树形结构及其相关算法。

7.1 创建节点

树形结构是由多个包含子节点内容的节点（Node）所组成的，也就是说树形结构由根节点开始至每一个叶节点为止，都是由同一种数据结构组成的。

一般来说，普通树形结构的节点由一个用于存储节点内容的空间，以及一个用于存储子节点的引用（在其他语言中也可以为指针）的数组所组成。

7.1.1 JavaScript 中的类（Class）

在学习如何创建一个树形结构的节点之前，我们需要首先来学习下如何使用 JavaScript 中的类语法，因为接下来非常多的数据应用开发中都离不开对类的使用。

类（Class）可以比喻为生物学中的物种，自然界中生物种类多得数不清，但是生物学家们却可以将它们逐一使用生物分类法 (opens new window)进行分类，就好比威猛凶悍的狮子、老虎再到惹人喜爱的花猫、橘猫无论从体型、毛色上都有着天差地别，但都同属猫科动物。也好比我们智人这一种族也有非常多的“亲戚”，而哪怕是我们智人本身也有黄种人、黑种人、白种人，人与人之间也有着千差万别的多样性。

而在计算机中也同样有着这样的多样性，有着若干个相同性质的对象，但各自却有着不同的特性、内容、参数等等。这就需要类来进行表示和实现这种特性。

我们再次将具体事物抽象化，我们每一个人都有各自的名字，我们都能表达自己的欢迎之词，那么就用一个 Person 类来表达我们共同的物种——智人。

class Person {
  constructor(name) {
    this.name = name
  }
  
  hello() {
    return 'Hello, my name is ' + this.name
  }
}

const me = new Person('Will')
console.log(me.hello()) //=> Hello, my name is Will

constructor 为构建函数，定义包含一个 name 参数以将其赋予这个人实例本身以作为其名字；hello 方法用于表达作为智人的友好欢迎之词。

脱离动物世界，回到人类社会文明中来，我们不仅拥有名字，还有着更为复杂的家族关系，我们都有一个家族名（Family Name）也就是我们的姓氏，以组成我们完整的姓名。

class Person {
  constructor(givenName, familyName) {
    this.givenName = givenName
    this.familyName = familyName
  }
  
  hello() {
    return `Hello, my name is ${this.givenName} ${this.familyName}`
  }
}

const me = new Person('Will', 'Gunn')
console.log(me.hello()) //=> Hello, my name is Will Gunn

在这个 Person 类中，我们定义了 givenName 和 familyName 两个属性，而在 JavaScript 的类中同时还允许定义虚拟属性，也就是 Getter。比如我们可以将姓与名结合在一起以组成我们的全名。

class Person {
  constructor(givenName, familyName) {
    this.givenName = givenName
    this.familyName = familyName
  }
  
  get fullName() {
    return `${this.givenName} ${this.familyName}`
  }
  
  hello() {
    return `Hello, my name is ${this.fullName}`
  }
}

const me = new Person('Will', 'Gunn')
console.log(me.hello()) //=> Hello, my name is Will Gunn

类所产生的实例都是一个对象，所以我们在第 3 节中时就已经说明了，对象是一种可以表达万物的技术。非常好，你已经学会了如何使用 JavaScript 的类来表达一种事物了，那么就让我们开始回到正题上，创建一个树形结构中的节点吧。

7.1.2 定义节点类型

一般情况下每一个节点都包含一个用于存储内容的容器，我们可以使用一个简单的 value 属性来表达；而对于子节点的引用则可以使用一个数组属性 children 来承载。

class Node {
  constructor(value) {
    this.value = value
    this.children = []
  }
}

const node = new Node('node value')

有了节点以后，就需要将多个节点组合起来了，比如将两个节点加入到另外一个节点中以作为其子节点。那么我们可以先为这个 Node 类添加一个 addChild 方法。

class Node {
  // ...
  
  addChild(node) {
    this.children.push(node)
    
    return this
  }
}

你可能会问，为什么不直接使用 node.children.push(childNode)，而非要在外面包一层 addChild 方法？别着急，事情远没有那么简单，我们后面会慢慢讲解。

const root = new Node('root')
const node1 = new Node('node 1')
const node2 = new Node('node 2')
const node3 = new Node('node 3')

root.addChild(node1).addChild(node2)
node1.addChild(node3)

这段代码中我们定义了四个节点，其中一个包含内容 root 的节点作为根节点，而节点 node 1 和 node 2 作为根节点的子节点，节点 node 3 作为节点 node 1 的子节点。从而形成了一棵非常简单的树形结构。

非常好，一个简单的树形已经构建出来了，那么接下来我们应该如何使用这棵树呢？一般来说每一种数据结构被发明出来就肯定会有其使用的方法和特征，就如数组结构有其长度特征 length，包含数字的数组则有平均值等等数学特征值。那么对于树形结构及其节点来说又有哪些特征值呢？

结构

树（Tree）

名称

翻译

解析

root

根

一棵树的根节点

结构

节点（Node）

名称

翻译

解析

parent

父节点

一个节点的父节点

children

子节点（复数）

一个节点的子节点集合

siblings

兄弟节点

与某一个节点拥有相同父节点的其他节点

degree

度

以某一节点为根节点的子树的个数，也可以简单地理解为子节点数目

depth

深度

一个节点的深度被定义为该节点到根节点之间边*数

height

高度

一个节点到距离它最远的叶节点**中间的边数

[ * ] 边：Edge，节点与节点直接的连接被定义为边
[ ** ] 叶节点：没有子节点的节点

在这份表格中你发现其实每一个节点还可以包含其父节点的信息，所以在之前的 Node 类中我们可以加入一个 parent 属性，以存储该节点的父节点。

而在前面定义的 addChild 方法中，我们就可以将定义父节点这个任务放在这里了。

class Node {
  constructor(name) {
    this.name = name
    this.parent = null // 默认一个节点在产生时为一个无父节点的根节点
    this.children = []
  }
  
  addChild(node) {
    node.parent = this
    this.children.push(node)
    
    return this
  }
}

7.1.3 扩展节点类型

Siblings 兄弟节点

当每一个节点有了其父节点的信息之后，就可以去尝试访问它的兄弟节点了，通过查询 node.parent.children 中的节点排除掉自己后便是它的兄弟节点。

class Node {

  // ...

  siblings() {
    const self = this
  
    if (this.parent) {
      return this.parent.children.filter(function(node) {
        return node !== self
      })
    } else {
      return []
    }
  }
}

const root = new Node('root')
const node1 = new Node('node 1')
const node2 = new Node('node 2')
const node3 = new Node('node 3')

root.addChild(node1).addChild(node2)
node1.addChild(node3)
console.log(node1.siblings()) //=> [Node{'node 2'}]

Degree 度

这个特征值的定义比较简单，在树形结构中，每一个节点的 degree 值就等于直接与它相连的子节点数。这里我们就可以用到前面学习到的“虚拟属性”了。

class Node {
  // ...
  
  get degree() {
    return this.children.length
  }
}

const root = new Node('root')
const node1 = new Node('node 1')
const node2 = new Node('node 2')

root.addChild(node1)
root.addChild(node2)

console.log(root.degree) //=> 2

Depth & Height 深度与高度

深度（Depth）和高度（Height）可以说是树形结构中比较抽象且很有意思的特征值了。深度的定义为从某一个节点到其所在的树形结构中的根节点所经过边的数目。

就好比上面的例子中，从节点 node 3 到节点 node 1 最后到根节点 root 中间经过了两个边，所以节点 node 3 的深度则为 2。这个在 JavaScript 中也是非常好实现的，只需不断检查经过的每一个父节点是否存在继续往根部走的父节点，并记录循环次数即可。当找到了没有父节点的节点时，则该节点就是这棵树的根节点，而循环次数便是目标节点的深度值。

class Node {

  // ...

  get depth() {
    let depth = 0
    let currNode = this

    while (currNode.parent != null) {
      depth++
      currNode = currNode.parent
    }

    return depth
  }

}

const root = new Node('root')
const node1 = new Node('node 1')
const node3 = new Node('node 3')

root.addChild(node1)
node1.addChild(node3)
console.log(node3.depth) //=> 2

而高度的定义则是以某一个节点为根所形成的树形结构（该树形结构可能是一棵更大的树形结构中的一部分，即子树）中，这个节点到最深的子节点中间经过的边的数目。

而深度和高度的关系，可以用一张图非常清晰的解释。

我们可以发现每一个节点的高度其实就是等于以该节点为根的的子树中，最深的一个子节点的深度。也就是说只要找到最深的一个子节点，并计算当前子树的深度即可。

但是我们前面在计算深度的时候是直接计算整棵树的深度，那么为了能够让每一个子节点都能够计算指定子树的深度，我们需要对前面的代码进行一些修改。

我们可以首先假设每一棵树的根目录都有一个虚拟的父节点 null，那么就直接在计算深度时候，将 currNode.parent != null 改成 currNode.parent != root，当 root 为 null 的时候将最后的结果加上 1 便是该节点到整棵树根节点的深度。

而为了能够将计算深度的算法使用在计算高度上，我们同时还需要将原本计算深度的算法提取出来，单独作为一个用于计算子树深度的方法。

class Node {

  // ...

  getDepthByRoot(root) {
    let depth = 0
    let currNode = this

    while (currNode.parent !== root) {
      depth++
      currNode = currNode.parent
    }

    return depth + 1
  }

  get depth() {
    return this.getDepthByRoot(null)
  }
}

那么问题来了，该如何找到一棵子树中的最深子节点呢？一般来说有两种方式，BFS（Breadth-first Search，广度优先搜索） (opens new window)和 DFS（Depth-first Search，深度优先搜索） (opens new window)，而因为 DFS 的宗旨就是“不撞南墙不回头”，为了算法实现的简易性，我们这里选择 BFS 作为实现的方式。

如何使用 BFS 找到最深的子节点？那便是逐层给节点编号，直到最后一个就是最深的节点。当然我们也没有必要真的为它们编号，只需按层级顺序找到最深的一个即可。

定义一个 FIFO（First In First Out，先进的先出）的队列，将每一个层的节点不断地推入到这个队列中，并不断取出前面被推入的节点，并检查是否有子节点，直到最后一个节点便是最深子节点。

class Node {

  // ...

  get height() {
    const queue = [ this ]
    let deepestNode = this

    while (queue.length > 0) {
      const len = queue.length

      for (let i = 0; i < len; ++i) {
        const currNode = queue.shift()

        deepestNode = currNode

        if (currNode.children.length > 0) {
          queue.push(...currNode.children)
        }
      }
    }

    return deepestNode.getDepthByRoot(this)
  }
}

const root = new Node('root')
const node1 = new Node('node 1')
const node2 = new Node('node 2')
const node3 = new Node('node 3')
const node4 = new Node('node 4')
const node5 = new Node('node 5')
const node6 = new Node('node 6')

root.addChild(node1)
root.addChild(node2)
node1.addChild(node3)
node1.addChild(node4)
node2.addChild(node5)
node5.addChild(node6)

console.log(root.height)  //=> 3
console.log(node1.height) //=> 1
console.log(node2.height) //=> 2

7.1.4 树形节点代码清单

最后我们便得到了一个完整的树形结构节点类，以用于完成一些我们需要的需求实现。

class Node {
  constructor(name) {
    this.name = name
    this.parent = null
    this.children = []
  }
  
  addChild(node) {
    node.parent = this
    this.children.push(node)

    return this
  }

  siblings() {
    const self = this
  
    if (this.parent) {
      return this.parent.children.filter(function(node) {
        return node !== self
      })
    } else {
      return []
    }
  }

  get degree() {
    return this.children.length
  }

  getDepthByRoot(root) {
    let depth = 0
    let currNode = this

    while (currNode.parent !== root) {
      depth++
      currNode = currNode.parent
    }

    return depth + 1
  }

  get depth() {
    return this.getDepthByRoot(null)
  }

  get height() {
    const queue = [ this ]
    let deepestNode = this

    while (queue.length > 0) {
      const len = queue.length

      for (let i = 0; i < len; ++i) {
        const currNode = queue.shift()

        deepestNode = currNode

        if (currNode.children.length > 0) {
          queue.push(...currNode.children)
        }
      }
    }

    return deepestNode.getDepthByRoot(this)
  }

  toString(join = true) {
    let parts = [ this.name ]

    if (this.children.length > 0) {
      parts = parts.concat(this.children
        .map(function(node) {
          return node.toString(false)
        })
        .reduce(function(left, right) {
          return left.concat(right)
        })
        .map(function(line) {
          return '  ' + line
        })
      )
    }

    if (join) {
      return parts.join('\n')
    } else {
      return parts
    }
  }
}

7.2 定义树形结构

完成了节点的定义后，事实上我们已经可以实现树形结构的定义，并将数据存储在节点上了。但就如数组和序列之类的数据结构那样，除了对单个元素的操作以外，还需要对整个数据结构进行处理和计算。

所以我们需要定义一个专用的树形类，命名为 Tree，以完成一些需要对整棵树进行的计算。

class Tree {

  constructor(root) {
    this.root = root
  }

  addNode(node, parent = this.root) {
    parent.addChild(node)
  }
  
}

创建一棵树时首先要传入一个根节点对象，还可以使用 tree.addNode 代替直接调用 node.addChild，并默认将传入的节点作为根节点的子节点，以便进行管理。

7.2.1 查询节点

当一个树形结构被其他程序创建好以后，通过各种方式传入到你的程序中。而你需要知道这棵树中是否包含某一节点时，就需要使用一些算法来实现这个需求了。

我们前面在实现寻找一棵树中最深子节点的时候用到了 BFS 搜索算法来实现为每一层的子节点进行编号，BFS 的好处是可以搜索到树形结构中的大部分分支。但如果说要找到树形结构中的特定的某一个节点，BFS 显然不是最优的方案。

那么从拓扑学的角度上看一棵树形结构，BFS 的概念便是横向搜索，而 DFS 则是纵向搜索，“不撞南墙不回头”。这种搜索方式的好处是在一棵广度非常大的树形结构中，一旦能找到符合的节点，就能结束对其他分支的搜索。

DFS 在实现上也并不困难，从根节点开始，不断往下搜索第一个子节点（因为在本小册中所使用的树形结构节点都只会使用数组来存储子节点，所以自带顺序结构）。如果符合要求则返回该节点，如果不符合则先检查是否存在下一层或检查下一个兄弟节点。这里我们配合使用第 4 节中所封装的 arrayUtils 进行实现。

class Tree {

  // ...

  search(validator) {
    const queue = [ this.root ]
    const result = []

    while (queue.length > 0) {
      const currNode = queue.shift()

      if (validator(currNode)) {
        result.push(currNode)
        continue
      }

      if (currNode.children.length > 0) {
        arrayUtils.prepend(queue, ...currNode.children)
      }
    }

    return result
  }
}

const root = new Node('root')
const node1 = new Node('node 1')
const node2 = new Node('node 2')
const node3 = new Node('node 3')
const node4 = new Node('node 4')
const node5 = new Node('node 5')
const node6 = new Node('node 6')

const tree = new Tree(root)
tree.addNode(node1)
tree.addNode(node2)
tree.addNode(node3, node1)
tree.addNode(node4, node1)
tree.addNode(node5, node2)
tree.addNode(node6, node5)

console.log(tree.search(function(node) {
  return node.name == 'node 4')
})) //=> [ Node{node 4} ]

7.2.2 统计树形大小

当我们使用各种程序来创建和扩展一棵树形结构之后，我们并不一定知道这棵树中究竟有多少节点，因为这些节点很有可能是由多个相互独立的程序所创建和插入的。那么我们就需要有一个方法来统计一棵树内究竟有多少节点（包括根节点）。

既然需要统计所有的节点，那必定要遍历整棵树以进行计数。而我们已经学会了使用 BFS 和 DFS 两种搜索方式了，那么我们可以使用其中的一种来进行遍历，并去掉其中的判断逻辑以遍历整棵树。这里我们先用我们刚刚学会的 DFS 来进行遍历统计。

class Tree {

  // ...

  get size() {
    let size = 0
    const bag = [ this.root ]

    while (bag.length > 0) {
      const currNode = bag.shift()

      size++

      if (currNode.children.length > 0) {
        arrayUtils.prepend(bag, ...currNode.children)
      }
    }

    return size
  }

}

const root = new Node('root')
const node1 = new Node('node 1')
const node2 = new Node('node 2')
const node3 = new Node('node 3')
const node4 = new Node('node 4')
const node5 = new Node('node 5')
const node6 = new Node('node 6')

const tree = new Tree(root)
tree.addNode(node1)
tree.addNode(node2)
tree.addNode(node3, node1)
tree.addNode(node4, node1)
tree.addNode(node5, node2)
tree.addNode(node6, node5)

console.log(tree.size) //=> 7

7.2.3 树形结构代码清单

class Tree {

  constructor(root) {
    this.root = root
  }

  addNode(node, parent = this.root) {
    parent.addChild(node)
  }

  search(validator) {
    const queue = [ this.root ]

    while (queue.length > 0) {
      const currNode = queue.shift()

      if (validator(currNode)) {
        return currNode
      }

      if (currNode.children.length > 0) {
        arrayUtils.prepend(queue, ...currNode.children)
      }
    }
  }

  get size() {
    let size = 0
    const bag = [ this.root ]

    while (bag.length > 0) {
      const currNode = bag.shift()

      size++

      if (currNode.children.length > 0) {
        arrayUtils.prepend(bag, ...currNode.children)
      }
    }

    return size
  }

  get height() {
    return this.root.height
  }
  
  toString() {
    return this.root.toString()
  }
}

小结

我们已经学会了创建一个树形结构并且如何对其进行操作和检索，虽然现在看来你可能还会对树形结构究竟能完成些什么实际需求感到疑惑。但是别着急，我们接下来会接触更多的数据结构，我们需要通过接触不同的数据结构来进行组合学习，才能更好地理解每一种数据结构的特点和使用场景。

习题

请使用 BFS 方法来实现统计树形结构中节点的数量。